package com.wenmingliang.linkedlist;

import java.util.Stack;

/**
 * @author wenmingliang
 * @create 2023/5/3
 */

/**
 * 单链表的反转操作
 */
public class LinkedList01 {

    /**
     *
     * @param head 头节点
     * @return newHeadNode: 新的单链表头节点
     */
    public static ListNode reverseList(ListNode head) {
        Stack<ListNode> listNodeStack = new Stack<>();
        ListNode p = head;
        ListNode t;
        while (p != null) {
            t = p.next;
            p.next = null;
            listNodeStack.add(p);
            p = t;
        }
        ListNode newHeadNode = listNodeStack.pop();
        ListNode q = newHeadNode;
        while (!listNodeStack.isEmpty()) {
            ListNode popNode = listNodeStack.pop();
            q.next = popNode;
            q = q.next;
        }

        return newHeadNode;
    }

    public static void main(String[] args) {
        // 初始化链表
        ListNode headNode = initListNode();
        // 输出初始化链表
        System.out.println(headNode);

        // 反转链表
        ListNode newHeadNode = reverseList(headNode);

        // 输出反转后的链表
        System.out.println(newHeadNode);

    }

    /**
     * 单链表的初始化
     * @return headNode: 为初始化单链表的头节点
     */
    private static ListNode initListNode() {
        ListNode headNode = new ListNode();
        headNode.val = 1;
        ListNode p = headNode;
        for (int i = 2; i < 11; i++) {
            ListNode listNode = new ListNode();
            listNode.val = i;
            p.next = listNode;
            p = listNode;
        }
        return headNode;
    }
}

/**
 * 单链表数据结构的定义
 */
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    public ListNode() {

    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
